#include <vector>

using namespace std;

class Solution {
public:
    // O(m + n)
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if (n == 0) return;
        for (int k=m+n-1; k>=0; k--) {
            if (m <= 0) break;
            if (n <= 0) break;
            if (nums1[m-1] > nums2[n-1]) {
                nums1[k] = nums1[--m];
            } else {
                nums1[k] = nums2[--n];
            }
        }
        while (n > 0) {
            nums1[n-1] = nums2[n-1];
            n--;
        }
    }
};
